package com.company.ljh.search;

import java.util.Arrays;

/**
 * @description: 2300. 咒语和药水的成功对数
 * @projectName:leet_code
 * @see:com.company.ljh.search
 * @author:ljh
 * @createTime:2023/10/17 16:18
 * @version:1.0
 */
public class MiddleSearch {
    public static void main(String[] args) {
        int i = midSearch(new int[]{1, 2, 3, 4, 5, 6}, 0, 0, 5);
        System.out.println(i);
    }
    /**
     * 对potition排序，然后二分查找最近一个小于当前数的位置
     * @param spells
     * @param potions
     * @param success
     * @return
     */
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int result[] = new int[spells.length];
        Arrays.sort(potions);
        for (int i = 0; i < spells.length; i++) {
            if (spells[i] == 0) {
                continue;
            }
            long target = (success / spells[i]) + 1;
            if ((success % (long) spells[i]) == 0l) {
                target--;
            }
            int num = potions.length - 1 - midSearch(potions, target, 0, potions.length - 1);
            result[i] = num;
        }
        return result;
    }

    /**
     * 二分查找最近一个小于当前数的位置
     * @param nums
     * @param target
     * @param start
     * @param end
     * @return
     */
    public static int midSearch(int nums[], long target, int start, int end) {
        int middle = start + (end - start) / 2;
        if (((long) nums[middle]) < target) {
            if (middle + 1 >= nums.length) {
                return nums.length - 1;
            }
            //当前数比target小，下一个比target大，返回结果
            if (((long) nums[middle + 1]) >= target) {
                return middle;
            } else {
                //继续查找后半截数据
                return midSearch(nums, target, middle + 1, end);
            }

        } else {
            if (middle == 0){
                //已经查找到第一个数
                return -1;
            }
            //当前数比target大，直接往前查找
            return midSearch(nums, target, start, middle);

        }

    }


}
